The present invention relates generally to fast Fourier transform (FFT) circuitry and, more particularly, to techniques for “pruning” FFT circuits to reduce both circuit complexity and power dissipation.
By way of brief background, the Fourier transform is a mathematical formula for converting a signal that varies with respect to time (a signal in the time domain), into a corresponding plot of spectral content of the same signal (a representation of the signal in the frequency domain). The discrete Fourier transform may be viewed as a special case of the continuous form of the Fourier transform. The DFT determines a set of spectrum amplitudes or coefficients from a time-varying signal defined by a periodic sequence of samples taken at discrete time intervals.
FFT technology has been known since the 1960s, when it was first recognized that the discrete Fourier transform (DFT) could be performed more rapidly using various mathematical techniques now known as the fast Fourier transform. The FFT is widely known and discussed in the technical literature and is used in a variety of signal processing applications in which there is a need to transform signals from the time domain to the frequency domain.
With the ongoing development of integrated circuit design and fabrication techniques, FFT circuits have been implemented as integrated circuits, more particularly those that are termed application-specific integrated circuits (ASICs). Regardless of the implementation techniques employed, there is often a design requirement to minimize circuit complexity and power dissipation in FFT circuits. A known approach for achieving this goal is to eliminate or “prune” circuit branches that do not contribute significantly to the required output of an FFT. More specifically, a particular FFT application may require fewer outputs from the circuit than the number resulting from the available inputs. For example, an eight-point FFT in general provides eight outputs, indicative of spectral content in eight spectral bands. The application may well need only four of the outputs, in which case the other four would be discarded. In accordance with the pruning technique, the FFT circuit is pruned during its design, to eliminate the unwanted branches and to produce only four outputs. In conventional FFT signal flow diagrams, it is typically the outer branches that are eliminated and the inner ones that are retained. However, there may be some applications of the FFT that call for elimination of branches all grouped on one side of the outputs. By eliminating branches, the circuit designer reduces circuit complexity, as measured, for example, by the number of logic gates in the circuit, and also reduces the total power dissipated by the circuit.
A significant drawback to this pruning technique is that it must be applied at the circuit design stage. Once a pruned FFT circuit has been fabricated, it can no longer be restored to its original state, i.e., before pruning. In other words, FFT circuits must be customized during design for specific applications. Reducing circuit complexity has become a lesser concern as the component density of integrated circuits has increased with improvements in fabrication techniques, but there is still a need to minimize power dissipation in many FFT applications. Therefore, it would be highly desirable to provide an FFT circuit that could be pruned for a specific application after its design and fabrication. The present invention is directed to this end.